package homework;

import code1.ArrayGenerator;
import code1.SortHelper;

import java.util.Arrays;
import java.util.Random;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/16 14:27
 * 基础快排---优化 --使用随机化的partition
 * 目标：生成一个[left,right]区间的随机值
 * 生成一个[0,right-left]区间的随机值
 * ==》left+[0,right-left]区间的随机值--》[left,right]区间的随机值
 *
 * 继续优化：只创建一个Random对象
 */
public class QuickSort3_1 {

    public static <E extends Comparable<E>>  void sort(E[] arr) {

        Random rd = new Random();
        quicksort(arr,0,arr.length-1,rd);
    }


    public static <E extends Comparable<E>>   void quicksort(E[] arr,int left,int right,Random rd){

        if(left > right) {
            return; //递归出口
        }
        int p=partition(arr,left,right,rd);
        quicksort(arr,left,p-1,rd);
        quicksort(arr,p+1,right,rd);


    }

    private static<E extends Comparable<E>> int partition(E[] arr, int left, int right,Random rd) {
//        [left,right]区间的随机值
        int p = left + (rd).nextInt(right-left+1);
        exchange(arr,left,p);




        E v = arr[left];
        int j  = left;
        for (int i = left+1; i <= right;i++ ) {
            if (arr[i].compareTo(v) < 0){
                j++;
                exchange(arr,i,j);
            }
//            大于就直接i++
        }
        //最后交换
        exchange(arr,left,j);

        return j;

    }

    private static  <E extends Comparable<E>> void exchange(E[] arr, int i, int j) {
        E temp=arr[i];
        arr[i] =arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[]  dataSize = {100000,1000000};
        for(int n:dataSize){
//            Integer[] array = ArrayGenerator.generateRandomArray(n, n);
            Integer[] array = ArrayGenerator.generateOrderedArray(n);
            Integer[]  copy = Arrays.copyOf(array,array.length);
            Integer[]  copy2 = Arrays.copyOf(array,array.length);
            Integer[]  copy3 = Arrays.copyOf(array,array.length);
//            SortHelper.sortTest("QuickSort",array);
//            SortHelper.sortTest("QuickSort2",copy);
            SortHelper.sortTest("QuickSort3",copy2);
            SortHelper.sortTest("QuickSort3_1",copy3);

            System.out.println("--------------------------------");
        }
        /**
         * QuickSort , n = 100000: 3.848171 s
         * QuickSort2 , n = 100000: 3.707599 s
         * QuickSort3 , n = 100000: 0.024743 s
         * QuickSort3_1 , n = 100000: 0.019533 s
         * --------------------------------
         */

    }


}
